#include <iostream>

using namespace std;
typedef long long LL;

LL qmi(int n, int k, int p)
{
    LL res = 1 % p;
    while (k)
    {
        if (k & 1)
        {
            res = res * n % p;
        }
        n = n * (LL)n % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    int n, k, q, m;
    cin >> m;
    while (m--)
    {
        scanf("%d %d %d", &n, &k, &q);
        printf("%d\n", qmi(n, k, q));
    }
    return 0;
}